package com.lmz.project.redis.arithmetic.dichotomy;

import com.lmz.project.redis.arithmetic.utils.ArrUtils;

import java.util.Arrays;

/**
 * 二分法学习
 */
public class DichotomyTest {


    /**
     * 暴力查询
     * @param arr 数组（有序）
     * @param target 目标数值
     * @return 是否存在
     */
    public static boolean searchNumViolence(int[] arr, int target){
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target){
                return true;
            }
        }
        return false;
    }

    /**
     * 判断目标数字是否在数组中存在
     *
     * @param arr 数组保证必须有序
     * @param target 目标数值
     * @return 是否存在
     */
    public static boolean searchNum(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target){
                return true;
            }else if (arr[mid] > target){
                right = mid -1;
            }else {
                left = mid + 1 ;
            }
        }
        return false;
    }

    //有序数组中找>=num的最左位置
    public static int searchLeftGreaterTar(int[] arr,int target){
        if (arr==null || arr.length==0){
            return -1;
        }
        int left = 0;
        int right = arr.length-1;
        int tarIndex = -1; //记录符合结果的下标为-1
        while (left <= right){
            int mid = left + (right -left)/2;
            if (mid>=target){
                tarIndex = mid; //更新结果位置
                right = mid-1; //继续下一轮循环,查看是否有更左侧的位置
            }else {
                left=mid=1;
            }
        }
        return tarIndex;
    }


    //有序数组找<=num的最右位置
    public static int searchRightLessTar(int[] arr,int target){
        if (arr==null || arr.length==0){
            return -1;
        }
        int left = 0;
        int right = arr.length-1;
        int tarIndex = -1; //记录符合结果的下标为-1
        while (left<=right){
            int mid = left + (right - left) /2;
            if (mid<=target){
                tarIndex = mid;
                left=mid+1;
            }else {
                right=mid-1;
            }
        }
        return tarIndex;
    }


    //二分法不一定是发生在有序数组上 （寻找峰值问题，但是必须保证数组必须两两之前不相等）
    public static int searchPeakValueIndex(int[] nums){
        int targetIndex=-1;
        if (nums == null || nums.length==0){
            return targetIndex;
        }
        if (nums.length == 1){
            return 0;
        }
        //以下是数组长度>=2的情况
        //判断0位置和最后一个位置是否是峰值,如果是直接返回
        if (nums[0]>nums[1]){
            return 0;
        }
        if (nums[nums.length-2]<nums[nums.length-1]){
            return nums.length-1;
        }
        //如果都不是,说明arr[0]< nums[1],上升,nums[nums.length-2] > nums[nums,length-1] 下降
        //中间必定出现峰值
        //使用二分法进行查找峰值
        int left = 1;
        int right = nums.length-2;
        while (left<=right){
            int mid = left + (right - left) /2;
            if (nums[mid]>nums[mid-1] && nums[mid]>nums[mid+1]){
                targetIndex = mid;
                break;
            }else if (nums[mid] > nums[mid-1]){
                //说明在右侧必定出现峰值
                left = mid+1;
            } else {
                right = mid -1;
            }
        }
        return targetIndex;
    }

    public static void main(String[] args) {
//        int maxV = 100;
//        int length = 10;
//        int testTimes = 100;
//        int target = 20;
//        System.out.println("开始执行");
//        for (int i = 0; i < testTimes; i++) {
//            int[] intArr = ArrUtils.createIntArr(maxV, length);
//            Arrays.sort(intArr);
//            boolean b = searchNum(intArr, target);
//            boolean b1 = searchNumViolence(intArr, target);
//            if (b!=b1){
//                System.out.println("执行出错");
//            }
//        }
//
//        System.out.println("执行完毕");
        //[1,2,3,1]
        int[] nums = {1,2,3,1};
        int i = searchPeakValueIndex(nums);
        System.out.println(i);

    }
}
